{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Missing Number"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Easy"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #bit-manipulation #array #hash-table #math #binary-search #sorting"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #位运算 #数组 #哈希表 #数学 #二分查找 #排序"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: missingNumber"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #丢失的数字"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>给定一个包含 <code>[0, n]</code>&nbsp;中&nbsp;<code>n</code>&nbsp;个数的数组 <code>nums</code> ，找出 <code>[0, n]</code> 这个范围内没有出现在数组中的那个数。</p>\n",
    "\n",
    "<ul>\n",
    "</ul>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>示例 1：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>nums = [3,0,1]\n",
    "<strong>输出：</strong>2\n",
    "<b>解释：</b>n = 3，因为有 3 个数字，所以所有的数字都在范围 [0,3] 内。2 是丢失的数字，因为它没有出现在 nums 中。</pre>\n",
    "\n",
    "<p><strong>示例 2：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>nums = [0,1]\n",
    "<strong>输出：</strong>2\n",
    "<b>解释：</b>n = 2，因为有 2 个数字，所以所有的数字都在范围 [0,2] 内。2 是丢失的数字，因为它没有出现在 nums 中。</pre>\n",
    "\n",
    "<p><strong>示例 3：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>nums = [9,6,4,2,3,5,7,0,1]\n",
    "<strong>输出：</strong>8\n",
    "<b>解释：</b>n = 9，因为有 9 个数字，所以所有的数字都在范围 [0,9] 内。8 是丢失的数字，因为它没有出现在 nums 中。</pre>\n",
    "\n",
    "<p><strong>示例 4：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>nums = [0]\n",
    "<strong>输出：</strong>1\n",
    "<b>解释：</b>n = 1，因为有 1 个数字，所以所有的数字都在范围 [0,1] 内。1 是丢失的数字，因为它没有出现在 nums 中。</pre>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>提示：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>n == nums.length</code></li>\n",
    "\t<li><code>1 &lt;= n &lt;= 10<sup>4</sup></code></li>\n",
    "\t<li><code>0 &lt;= nums[i] &lt;= n</code></li>\n",
    "\t<li><code>nums</code> 中的所有数字都 <strong>独一无二</strong></li>\n",
    "</ul>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>进阶：</strong>你能否实现线性时间复杂度、仅使用额外常数空间的算法解决此问题?</p>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [missing-number](https://leetcode.cn/problems/missing-number/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [missing-number](https://leetcode.cn/problems/missing-number/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['[3,0,1]', '[0,1]', '[9,6,4,2,3,5,7,0,1]']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def missingNumber(self, arr: List[int]) -> int:\n",
    "        arr.sort()\n",
    "        diff = min(arr[1] - arr[0], arr[-1] - arr[-2])\n",
    "\n",
    "        for i in range(len(arr) - 1):\n",
    "                if arr[i + 1] - arr[i] > diff:\n",
    "                    return arr[i] + diff\n",
    "        return arr[0]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def missingNumber(self, arr: List[int]) -> int:\n",
    "        n = len(arr)\n",
    "        l = 0\n",
    "        r = n-1\n",
    "        diff = (arr[r]-arr[l])/n\n",
    "        while l < r:\n",
    "            m = (l+r)//2\n",
    "            if arr[m] == arr[0] + m*diff:\n",
    "                l = m+1\n",
    "            else:\n",
    "                r = m\n",
    "        return int(arr[0] + diff*l)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def missingNumber(self, arr: List[int]) -> int:\n",
    "        return (arr[0] + arr[-1]) * (len(arr) + 1) // 2 - sum(arr)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def missingNumber(self, arr: List[int]) -> int:\n",
    "        arr.sort()\n",
    "        diff = min(arr[1] - arr[0], arr[-1] - arr[-2])\n",
    "\n",
    "        for i in range(len(arr) - 1):\n",
    "                if arr[i + 1] - arr[i] > diff:\n",
    "                    return arr[i] + diff\n",
    "        return arr[0]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def missingNumber(self, arr: List[int]) -> int:\n",
    "        n = len(arr)\n",
    "        d = (arr[-1] - arr[0]) // n\n",
    "        return (n + 1) * arr[0] + n * (n + 1) * d // 2 - sum(arr)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def missingNumber(self, arr: List[int]) -> int:\n",
    "        diff = (arr[-1]-arr[0])//len(arr)\n",
    "        for i in range(0,len(arr)-1):\n",
    "            if arr[i+1]!=arr[i]+diff:\n",
    "                return arr[i]+diff\n",
    "        return arr[0]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def missingNumber(self, arr: List[int]) -> int:\n",
    "        arr_len = len(arr)\n",
    "        diff = (arr[-1] - arr[0]) // arr_len\n",
    "\n",
    "        left = 0\n",
    "        right = arr_len - 1\n",
    "\n",
    "        while left < right:\n",
    "            mid = (left + right) // 2\n",
    "            if arr[mid] == arr[0] + mid * diff:\n",
    "                left = mid + 1\n",
    "            else:\n",
    "                right = mid\n",
    "\n",
    "        return arr[0] + diff * left\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def missingNumber(self, arr: List[int]) -> int:\n",
    "        sub = (arr[-1]-arr[0])/(len(arr))\n",
    "        for item in arr:\n",
    "            if item + sub in arr:\n",
    "                pass\n",
    "            else:\n",
    "                return int(item+sub)\n",
    "        \n",
    "                \n",
    "        return arr[0]\n",
    "                "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def missingNumber(self, arr: List[int]) -> int:\n",
    "        return (arr[0] + arr[-1]) * (len(arr) + 1) // 2 - sum(arr)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def missingNumber(self, arr: List[int]) -> int:\n",
    "        l = 0\n",
    "        r = len(arr) - 1\n",
    "        while r - l > 1:\n",
    "            mid = l + (r - l) // 2\n",
    "            if abs(arr[mid] - arr[l]) / (mid - l) > abs(arr[r] - arr[mid]) / (r - mid):\n",
    "                r = mid\n",
    "            else:\n",
    "                l = mid\n",
    "        return (arr[l] + arr[r]) // 2\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def missingNumber(self, arr: List[int]) -> int:\n",
    "        return (arr[0] + arr[-1]) * (len(arr)+1) // 2 - sum(arr)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def missingNumber(self, arr: List[int]) -> int:\n",
    "        # 题目说了不可能是第一个和最后一个位置\n",
    "        lo, hi = 0, len(arr) - 1\n",
    "        diff = (arr[-1] - arr[0]) // len(arr)\n",
    "        while lo < hi - 1:\n",
    "            mid = lo + (hi - lo + 1) // 2\n",
    "            if arr[mid] - arr[lo] == diff * (mid - lo):\n",
    "                lo = mid\n",
    "            else:\n",
    "                hi = mid\n",
    "        \n",
    "        return (arr[lo] + arr[hi]) // 2\n",
    "\n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def missingNumber(self, arr: List[int]) -> int:\n",
    "        target = (arr[-1]-arr[0])/len(arr)\n",
    "        lo = 0\n",
    "        hi = len(arr)-1\n",
    "        while(lo<hi):\n",
    "            mid = math.floor((hi+lo)/2)\n",
    "            if arr[mid] == arr[0] +mid*target:\n",
    "                lo = mid+1\n",
    "            else:\n",
    "                hi = mid\n",
    "        return int(arr[0]+target*lo)\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def missingNumber(self, arr: List[int]) -> int:\n",
    "        n = len(arr)\n",
    "\n",
    "        diff = (arr[-1] - arr[0]) // n \n",
    "\n",
    "        left, right = 0, len(arr) - 1\n",
    "        while left < right:\n",
    "            mid = (left + right) // 2\n",
    "            if arr[mid] == arr[0] + mid * diff:\n",
    "                left = mid + 1\n",
    "            else:\n",
    "                right = mid \n",
    "        \n",
    "        return arr[0] + diff * left  \n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def missingNumber(self, arr: List[int]) -> int:\n",
    "        start, end = arr[0], arr[-1]\n",
    "        dif = int(abs(start - end) / len(arr))\n",
    "        if start == end:\n",
    "            return start\n",
    "\n",
    "        for i in range(len(arr) - 1):\n",
    "            if abs(arr[i] - arr[i + 1]) != dif:\n",
    "                if arr[i] > arr[i + 1]:\n",
    "                    return arr[i] - dif\n",
    "                else:\n",
    "                    return arr[i] + dif\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def missingNumber(self, arr: List[int]) -> int:\n",
    "        return (len(arr) + 1) * (arr[0] + arr[-1]) // 2 - sum(arr)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def missingNumber(self, arr: List[int]) -> int:\n",
    "        # 题目说了不可能是第一个和最后一个位置\n",
    "        lo, hi = 0, len(arr) - 1\n",
    "        diff = (arr[-1] - arr[0]) // len(arr)\n",
    "        while lo < hi:\n",
    "            mid = lo + (hi - lo) // 2\n",
    "            if arr[mid] == arr[0] + diff * mid:\n",
    "                lo = mid + 1\n",
    "            else:\n",
    "                hi = mid\n",
    "        \n",
    "        return arr[0] + diff * lo\n",
    "\n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def missingNumber(self, arr: List[int]) -> int:\n",
    "        diff = (arr[len(arr)-1] - arr[0]) // len(arr)\n",
    "        if diff == 0:\n",
    "            return arr[0]\n",
    "\n",
    "        left, right = 0, len(arr)-1\n",
    "\n",
    "        while left < right:\n",
    "            mid = (left + right) // 2\n",
    "            if arr[mid] - arr[0] == diff * mid:\n",
    "                left = mid + 1\n",
    "            else:\n",
    "                right = mid\n",
    "        return arr[0] + left * diff"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def missingNumber(self, arr: List[int]) -> int:\n",
    "        # 这里使用二分查找可以快速确认缺失的值在哪边，主要是算法怎么写\n",
    "        arr_len = len(arr)\n",
    "        diff = (arr[-1] - arr[0]) // arr_len\n",
    "        # 二分查找\n",
    "        start, end = 0, arr_len - 1\n",
    "        while start < end:\n",
    "            m = (end + start) // 2\n",
    "            if arr[m] != arr[0] + m*diff:\n",
    "                end = m\n",
    "            else:\n",
    "                start = m\n",
    "            if end - start == 1:\n",
    "                return arr[0] + end*diff\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def missingNumber(self, arr: List[int]) -> int:\n",
    "        n = len(arr)\n",
    "        d = (arr[-1] - arr[0]) // n\n",
    "        l, r = 0, n - 1\n",
    "        while l < r:\n",
    "            mid = l + r + 1 >> 1\n",
    "            if arr[mid] == arr[0] + d * mid:\n",
    "                l = mid\n",
    "            else:\n",
    "                r = mid - 1\n",
    "        return arr[l] + d"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def missingNumber(self, arr: List[int]) -> int:\n",
    "        arr.sort()\n",
    "        diff = min(arr[1] - arr[0], arr[-1] - arr[-2])\n",
    "\n",
    "        for i in range(len(arr) - 1):\n",
    "                if arr[i + 1] - arr[i] > diff:\n",
    "                    return arr[i] + diff\n",
    "        return arr[0]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def missingNumber(self, arr: List[int]) -> int:\n",
    "        \n",
    "        sum_true = (arr[0]+arr[-1])*(len(arr)+1)\n",
    "        sum_true/=2\n",
    "        result = sum_true - sum(arr)\n",
    "        return int(result)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def missingNumber(self, arr: List[int]) -> int:\n",
    "        arr.sort()\n",
    "        diff = min(arr[1] - arr[0], arr[-1] - arr[-2])\n",
    "\n",
    "        for i in range(len(arr) - 1):\n",
    "                if arr[i + 1] - arr[i] > diff:\n",
    "                    return arr[i] + diff\n",
    "                elif arr[i + 1] - arr[i] == 0:\n",
    "                    return arr[i]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def missingNumber(self, arr: List[int]) -> int:\n",
    "        return (arr[0] + arr[-1]) * (len(arr) + 1) // 2 - sum(arr)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def missingNumber(self, arr: List[int]) -> int:\n",
    "        interval_left_right = dict()\n",
    "        for i in range(len(arr)-1):\n",
    "            left, right = arr[i], arr[i+1]\n",
    "            interval_left_right[right-left] = (left, right)\n",
    "        k = max(interval_left_right.keys(), key=lambda x:abs(x)) \n",
    "        return interval_left_right[k][0]+k//2\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def missingNumber(self, arr: List[int]) -> int:\n",
    "        arr.sort()\n",
    "        diff = min(arr[1] - arr[0], arr[-1] - arr[-2])\n",
    "\n",
    "        for i in range(len(arr) - 1):\n",
    "                if arr[i + 1] - arr[i] > diff:\n",
    "                    return arr[i] + diff\n",
    "                elif arr[i + 1] - arr[i] == 0:\n",
    "                    return arr[i]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def missingNumber(self, arr: List[int]) -> int:\n",
    "        n=len(arr)\n",
    "        sum1=(arr[0]+arr[-1])*(n+1)//2\n",
    "        sum2=sum(arr)\n",
    "        num=sum1-sum2\n",
    "        return num"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def missingNumber(self, arr: List[int]) -> int:\n",
    "        a = arr[1] - arr[0]\n",
    "        b = arr[-1] - arr[-2]\n",
    "\n",
    "        if a > 0:\n",
    "            diff = min(a, b)\n",
    "        else:\n",
    "            diff = max(a, b)\n",
    "\n",
    "        for i in range(len(arr) - 1):\n",
    "            if diff > 0:\n",
    "                if arr[i + 1] - arr[i] > diff:\n",
    "                    return arr[i] + diff\n",
    "            else:\n",
    "                if arr[i + 1] - arr[i] < diff:\n",
    "                    return arr[i] + diff\n",
    "        return arr[0]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def missingNumber(self, arr: List[int]) -> int:\n",
    "        arr.sort()\n",
    "        diff = min(arr[1] - arr[0], arr[-1] - arr[-2])\n",
    "\n",
    "        for i in range(len(arr) - 1):\n",
    "                if arr[i + 1] - arr[i] > diff:\n",
    "                    return arr[i] + diff\n",
    "        return arr[0]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def missingNumber(self, arr: List[int]) -> int:\n",
    "        start, end = arr[0], arr[-1]\n",
    "        dif = int(abs(start - end) / len(arr))\n",
    "        if start == end:\n",
    "            return start\n",
    "\n",
    "        for i in range(len(arr) - 1):\n",
    "            if abs(arr[i] - arr[i + 1]) != dif:\n",
    "                if arr[i] > arr[i + 1]:\n",
    "                    return arr[i] - dif\n",
    "                else:\n",
    "                    return arr[i] + dif\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def missingNumber(self, arr: List[int]) -> int:\n",
    "        \n",
    "        for i in range(len(arr)-2):\n",
    "            diff1 = arr[i+1] - arr[i]\n",
    "            diff2 = arr[i+2] - arr[i+1]\n",
    "            if abs(diff2) > abs(diff1):\n",
    "                return arr[i+1] + diff1\n",
    "            elif abs(diff2) < abs(diff1):\n",
    "                return arr[i] + diff2 \n",
    "        return arr[0]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def missingNumber(self, arr: List[int]) -> int:\n",
    "        arr.sort()\n",
    "        diff = min(arr[1] - arr[0], arr[-1] - arr[-2])\n",
    "\n",
    "        for i in range(len(arr) - 1):\n",
    "                if arr[i + 1] - arr[i] > diff:\n",
    "                    return arr[i] + diff\n",
    "                elif arr[i + 1] - arr[i] == 0:\n",
    "                    return arr[i]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def missingNumber(self, arr: List[int]) -> int:\n",
    "\n",
    "        n = len(arr)\n",
    "        d = (arr[-1] - arr[0])//len(arr) #由于收尾肯定不是缺失的数，因此可以计算出公差d\n",
    "        l = 0\n",
    "        r = n-1\n",
    "        while l<=r:  #利用二分的思想\n",
    "            mid = (l+r)>>1\n",
    "            if mid+1<n: #限定范围\n",
    "                if arr[mid+1]-arr[mid] !=d:\n",
    "                    return arr[mid]+d\n",
    "            elif mid-1>0:#限定范围\n",
    "                if arr[mid]-arr[mid-1] !=d:\n",
    "                    return arr[mid-1]+d\n",
    "            \n",
    "            if arr[mid]-arr[l] == (mid-l)*d: #说明在[mid,r]中 \n",
    "                l = mid+1\n",
    "            else: # 那么一定在说明在[l,mid]中 \n",
    "                r = mid-1\n",
    "        return arr[r]+d"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def missingNumber(self, arr: List[int]) -> int:\n",
    "        total = (arr[0] + arr[-1])* (len(arr) + 1) //2\n",
    "        return total - sum(arr)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def missingNumber(self, arr: List[int]) -> int:\n",
    "        arr.sort()\n",
    "        diff = min(arr[1] - arr[0], arr[-1] - arr[-2])\n",
    "\n",
    "        for i in range(len(arr) - 1):\n",
    "                if arr[i + 1] - arr[i] > diff:\n",
    "                    return arr[i] + diff\n",
    "        return arr[0]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def missingNumber(self, arr: List[int]) -> int:\n",
    "        return self.answer_1(arr)\n",
    "\n",
    "    def answer_1(self, arr):\n",
    "        arr_len = len(arr)\n",
    "\n",
    "        diff = (arr[-1] - arr[0]) // arr_len\n",
    "\n",
    "        for index in range(arr_len - 1, 0, -1):\n",
    "            if arr[index] - arr[index - 1] != diff:\n",
    "                return arr[index] - diff\n",
    "        return arr[0]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def missingNumber(self, arr: List[int]) -> int:\n",
    "        n = len(arr)\n",
    "        diff = (arr[-1] - arr[0]) // n\n",
    "\n",
    "        for i, num in enumerate(arr):\n",
    "            if num  != arr[0] + diff * i:\n",
    "                return arr[0] + diff * i\n",
    "        return arr[0]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def missingNumber(self, arr: List[int]) -> int:\n",
    "        n = len(arr)\n",
    "        left, right = 0, n\n",
    "        dis = (arr[-1]-arr[0]) / (n)\n",
    "        while left < right:\n",
    "            mid = (right-left) // 2 + left\n",
    "            if arr[mid] == arr[0] + (mid) * dis:\n",
    "                left = mid + 1\n",
    "            else:\n",
    "                right = mid\n",
    "        return int(arr[0] + left * dis)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def missingNumber(self, arr: List[int]) -> int:\n",
    "        diff = (arr[-1] - arr[0]) // len(arr)\n",
    "        l, r = 0, len(arr) - 1\n",
    "        while l<r:\n",
    "            mid = (l + r)//2\n",
    "            if arr[mid] == arr[0] + mid*diff:\n",
    "                l = mid + 1\n",
    "            else:\n",
    "                r = mid\n",
    "        \n",
    "        return arr[0] + r*diff\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from typing import List\n",
    "\n",
    "class Solution:\n",
    "    def missingNumber(self, arr: List[int]) -> int:\n",
    "        d = (arr[-1] - arr[0]) // len(arr)\n",
    "        if d == 0:\n",
    "            return arr[0]\n",
    "        left, right = 0, len(arr)-1\n",
    "        mid = (left + right) // 2\n",
    "        while mid != left:\n",
    "            if arr[mid] - arr[left] == (mid - left) * d:\n",
    "                left = mid\n",
    "            else:\n",
    "                right = mid\n",
    "            mid = (left + right) // 2\n",
    "        return arr[mid] + d"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def missingNumber(self, arr: List[int]) -> int:\n",
    "        a = arr[1] - arr[0]\n",
    "        for i in range(2, len(arr)):\n",
    "            b = arr[i] - arr[i-1]\n",
    "            if abs(a) < abs(b):\n",
    "                return arr[i-1] + a\n",
    "            elif abs(a) > abs(b):\n",
    "                return arr[0] + b\n",
    "            else:\n",
    "                pass\n",
    "        return arr[0]\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def missingNumber(self, arr: List[int]) -> int:\n",
    "        a = arr[1] - arr[0]\n",
    "        b = arr[-1] - arr[-2]\n",
    "\n",
    "        if a > 0:\n",
    "            diff = min(a, b)\n",
    "        else:\n",
    "            diff = max(a, b)\n",
    "\n",
    "        for i in range(len(arr) - 1):\n",
    "            if diff > 0:\n",
    "                if arr[i + 1] - arr[i] > diff:\n",
    "                    return arr[i] + diff\n",
    "            else:\n",
    "                if arr[i + 1] - arr[i] < diff:\n",
    "                    return arr[i] + diff\n",
    "        return arr[0]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def missingNumber(self, arr: List[int]) -> int:\n",
    "        s = (arr[0]+arr[-1])*(len(arr)+1)//2\n",
    "        return s-sum(arr)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def missingNumber(self, arr: List[int]) -> int:\n",
    "        n = len(arr)\n",
    "        d = (arr[-1] - arr[0])//len(arr) #由于收尾肯定不是缺失的数，因此可以计算出公差d\n",
    "        l = 0\n",
    "        r = n-1\n",
    "        while l<=r:  #利用二分的思想\n",
    "            mid = (l+r)>>1\n",
    "            if mid+1<n: #限定范围\n",
    "                if arr[mid+1]-arr[mid] !=d:\n",
    "                    return arr[mid]+d\n",
    "            elif mid-1>0:#限定范围\n",
    "                if arr[mid]-arr[mid-1] !=d:\n",
    "                    return arr[mid-1]+d\n",
    "            \n",
    "            if arr[mid]-arr[l] == (mid-l)*d: #说明在[mid,r]中 \n",
    "                l = mid+1\n",
    "            else: # 那么一定在说明在[l,mid]中 \n",
    "                r = mid-1\n",
    "        return arr[r]+d"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def missingNumber(self, arr: List[int]) -> int:\n",
    "        return int((arr[0]+arr[-1])/2 *(len(arr)+1) - sum(arr))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def missingNumber(self, arr: List[int]) -> int:\n",
    "        arr.sort()\n",
    "\n",
    "        diff = min(abs(arr[1] - arr[0]), abs(arr[1] - arr[2]))\n",
    "        if arr[1] == arr[0]:\n",
    "            return arr[0]\n",
    "        for i in range(1, len(arr)):\n",
    "            if arr[i - 1] + diff != arr[i]:\n",
    "                return arr[i - 1] + diff\n",
    "        return -1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def missingNumber(self, arr: List[int]) -> int:\n",
    "        n = len(arr)\n",
    "        cnt = Counter()\n",
    "        for x, y in pairwise(arr):\n",
    "            cnt[x - y] += 1\n",
    "        \n",
    "        mx = 0\n",
    "        for k in cnt:\n",
    "            if cnt[k] > mx:\n",
    "                mx = cnt[k]\n",
    "                d = k\n",
    "            elif cnt[k] == mx:\n",
    "                if abs(k) < abs(d):\n",
    "                    d = k\n",
    "        for x, y in pairwise(arr):\n",
    "            if x - y == d: continue\n",
    "            return x - d \n",
    "        return arr[0]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def missingNumber(self, arr: List[int]) -> int:\n",
    "        n = len(arr)\n",
    "        diff = (arr[-1] - arr[0]) // n\n",
    "\n",
    "        l, r = 0, n - 1\n",
    "        while l < r:\n",
    "            mid = (l + r) // 2\n",
    "            if arr[mid] == arr[0] + mid * diff:\n",
    "                l = mid + 1\n",
    "            else:\n",
    "                r = mid\n",
    "        return arr[l] - diff"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def missingNumber(self, arr: List[int]) -> int:\n",
    "        n = len(arr)\n",
    "        d = (arr[-1] - arr[0]) // n \n",
    "        l, r = 0, n - 1\n",
    "        while l + 1 < r:\n",
    "            mid = (l + r) // 2\n",
    "            if arr[mid] - arr[l] == d * (mid - l):\n",
    "                l = mid\n",
    "            else:\n",
    "                r = mid\n",
    "        return (arr[l] + arr[r]) // 2"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def missingNumber(self, arr: List[int]) -> int:\n",
    "        \n",
    "        delta = min([arr[1] - arr[0], arr[-1] - arr[-2]], key=lambda x: abs(x))\n",
    "        if delta == 0:\n",
    "            return arr[0]\n",
    "     \n",
    "        for i, a in enumerate(arr):\n",
    "            if delta + a != arr[i+1]:\n",
    "                return delta + a            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def missingNumber(self, arr: List[int]) -> int:\n",
    "        n = len(arr)\n",
    "        diff = arr[1]-arr[0]\n",
    "        if diff==0:\n",
    "            return arr[0]\n",
    "        for i in range(1,n-1):\n",
    "            sub = arr[i+1]-arr[i]\n",
    "            if abs(diff)<abs(sub):\n",
    "                index = i+1\n",
    "                break\n",
    "            if abs(diff)>abs(sub):\n",
    "                index = i\n",
    "                break\n",
    "        return (arr[index]+arr[index-1])//2"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def missingNumber(self, arr: List[int]) -> int:\n",
    "        # 二分查找\n",
    "        diff = (arr[-1] - arr[0]) // len(arr)\n",
    "        if diff == 0: return arr[0]\n",
    "        left, right = 0, len(arr) - 1\n",
    "        while left < right:\n",
    "            mid = (left + right) // 2\n",
    "            if arr[mid] == arr[0] + mid * diff:\n",
    "                left = mid + 1\n",
    "            else:\n",
    "                right = mid\n",
    "        return arr[right] - diff"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def missingNumber(self, arr: List[int]) -> int:\n",
    "        arr.sort()\n",
    "        if len(set(arr)) == 1:\n",
    "            return arr[0]\n",
    "        n = len(arr)\n",
    "        diff = (arr[-1] - arr[0]) // n\n",
    "        start = arr[0]\n",
    "        while start < arr[-1]:\n",
    "            if start + diff not in arr:\n",
    "                return start + diff\n",
    "            start += diff"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def missingNumber(self, nums: List[int]) -> int:\n",
    "        shown = [False]*(len(nums)+1)\n",
    "        for num in nums:\n",
    "            shown[num] = True\n",
    "        for i in range(len(nums)+1):\n",
    "            if not shown[i]:\n",
    "                return i"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def missingNumber(self, nums: List[int]) -> int:\n",
    "        s1 = set(nums)\n",
    "        s2 = set(range(len(nums)+1))\n",
    "        return list(s2-s1)[0]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import collections \n",
    "class Solution:\n",
    "    def missingNumber(self, nums: List[int]) -> int:\n",
    "        a=Counter(list(range(len(nums)+1)))\n",
    "        nums=Counter(nums)\n",
    "        return list((a-nums).keys())[0]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def missingNumber(self, nums: List[int]) -> int:\n",
    "        return list(set(range(0,len(nums)+1))-set(nums))[0]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def missingNumber(self, nums: List[int]) -> int:\n",
    "        res = len(nums)\n",
    "        for i in range(res):\n",
    "            res^=(i^nums[i])\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def missingNumber(self, nums: List[int]) -> int:\n",
    "        n=len(nums)\n",
    "        nums=set(nums)\n",
    "        a=set([i for i in range(n+1)])\n",
    "        b=list(a-nums)\n",
    "        return b[0]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def missingNumber(self, nums: List[int]) -> int:\n",
    "        res = set(list(range(len(nums)+1)))\n",
    "        return list(res.difference(set(nums)))[0]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def missingNumber(self, nums: List[int]) -> int:\n",
    "        n = len(nums) \n",
    "        total = n * (n + 1) // 2\n",
    "        now_t = sum(nums)\n",
    "        return total - now_t"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def missingNumber(self, nums: List[int]) -> int:\n",
    "        res = len(nums)\n",
    "        for i in range(len(nums)):\n",
    "            res^=(i^nums[i])\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def missingNumber(self, nums: List[int]) -> int:\n",
    "        sumList = 0\n",
    "        sumNum = 0\n",
    "        for i,num in enumerate(nums):\n",
    "            sumList += i\n",
    "            sumNum += num\n",
    "        return sumList+i+1-sumNum"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def missingNumber(self, nums: List[int]) -> int:\n",
    "        s = 0\n",
    "        for i, num in enumerate(nums):\n",
    "            s += i + 1\n",
    "            s -= num\n",
    "        return s"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def missingNumber(self, nums: List[int]) -> int:\n",
    "        n=len(nums)\n",
    "        total=(1+n)*n//2\n",
    "        arrSum=sum(nums)\n",
    "        return total-arrSum"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def missingNumber(self, nums: List[int]) -> int:\n",
    "        l = [0] * (len(nums) + 1)\n",
    "        for i in nums:\n",
    "            l[i] += 1\n",
    "        for i in range(len(l)):\n",
    "            if l[i] == 0: return i"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def missingNumber(self, nums: List[int]) -> int:\n",
    "        res = len(nums)\n",
    "        for i in range(len(nums)):\n",
    "            res^=(i^nums[i])\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def missingNumber(self, nums: List[int]) -> int:\n",
    "        res_all = []\n",
    "        for i in range(0,len(nums)+1):\n",
    "            if i not in nums:\n",
    "                return i\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def missingNumber(self, nums: List[int]) -> int:\n",
    "        res = len(nums)\n",
    "        for i in range(res):\n",
    "            res^=(i^nums[i])\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def missingNumber(self, nums: List[int]) -> int:\n",
    "        return sum(range(len(nums)+1)) - sum(nums)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def missingNumber(self, nums: List[int]) -> int:\n",
    "        nums.sort()\n",
    "        n=len(nums)\n",
    "        left,right=0,n-1\n",
    "        for i in range(n):\n",
    "            if i!=nums[i]:\n",
    "                return i\n",
    "        # 如果前面全都对，那就是最后一个值缺失了，排序后的nums[-1]+1\n",
    "        # return nums[-1]+1\n",
    "        return len(nums)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def missingNumber(self, nums: List[int]) -> int:\n",
    "        return (len(nums) * (len(nums) + 1) // 2) - sum(nums)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def missingNumber(self, nums: List[int]) -> int:\n",
    "        len_nums = len(nums)\n",
    "        for i in range(len_nums + 2):\n",
    "            if i not in nums:\n",
    "                return i"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def missingNumber(self, nums: List[int]) -> int:\n",
    "        nums.sort()\n",
    "        if nums[-1] != len(nums):\n",
    "            return len(nums)\n",
    "        if 0 not in nums:\n",
    "            return 0\n",
    "        check = nums[0]\n",
    "        for i in range(len(nums)):\n",
    "            if nums[i] - i != check:\n",
    "                return i+check\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def missingNumber(self, nums: List[int]) -> int:\n",
    "        s = set(nums)\n",
    "        for i in range(len(nums) + 1):\n",
    "            if i not in s:\n",
    "                return i\n",
    "\n",
    "class Solution:\n",
    "    def missingNumber(self, nums: List[int]) -> int:\n",
    "        n = len(nums)\n",
    "        total = n * (n + 1) // 2\n",
    "        arrSum = sum(nums)\n",
    "        return total - arrSum\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def missingNumber(self, nums: List[int]) -> int:\n",
    "        ans = len(nums)\n",
    "        for i, num in enumerate(nums):\n",
    "            ans ^= i ^ num\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def missingNumber(self, nums: List[int]) -> int:\n",
    "        n = len(nums)\n",
    "        total = n * (n + 1) // 2\n",
    "        current = sum(nums)\n",
    "        return total - current"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def missingNumber(self, nums: List[int]) -> int:\n",
    "        a=len(nums)\n",
    "        b=(a*(a+1))//2\n",
    "        c=sum(nums)\n",
    "        sum1=b-c\n",
    "        return sum1\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def missingNumber(self, nums: List[int]) -> int:\n",
    "        n = len(nums)\n",
    "\n",
    "        sum = 0\n",
    "        for i in range(0, len(nums)):\n",
    "            sum += nums[i]\n",
    "\n",
    "        true_sum = n*(n+1)*0.5\n",
    "        return int(true_sum - sum)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def missingNumber(self, nums: List[int]) -> int:\n",
    "        n = len(nums)\n",
    "        sums = n * (n+1) // 2\n",
    "        for num in nums:\n",
    "            sums -= num \n",
    "        return sums"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def missingNumber(self, nums: List[int]) -> int:\n",
    "        nums.sort()\n",
    "        n=len(nums)\n",
    "        left,right=0,n-1\n",
    "        for i in range(n):\n",
    "            if i!=nums[i]:\n",
    "                return i\n",
    "\n",
    "        # 如果前面全都对，那就是最后一个值缺失了，排序后的nums[-1]+1\n",
    "        # return nums[-1]+1\n",
    "        return len(nums)\n",
    "class Solution:\n",
    "    def missingNumber(self, nums: List[int]) -> int:\n",
    "        nums.sort()\n",
    "        n=len(nums)\n",
    "        left,right=0,n\n",
    "        while left<right:\n",
    "            mid=(left+right)//2\n",
    "            if mid==nums[mid]:\n",
    "                left+=1\n",
    "            elif mid<nums[mid]:\n",
    "                right=mid\n",
    "        return left"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def missingNumber(self, nums: List[int]) -> int:\n",
    "        maxn = len(nums)\n",
    "        return int((0+maxn) * (len(nums)+1)/2 - sum(nums))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def missingNumber(self, nums: List[int]) -> int:\n",
    "        nums.sort()\n",
    "        for i in range(0,len(nums)):\n",
    "            if i != nums[i]:\n",
    "                return i\n",
    "        return i+1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def missingNumber(self, nums: List[int]) -> int:\n",
    "        n=len(nums)\n",
    "        total=(1+n)*n//2\n",
    "        arrSum=sum(nums)\n",
    "        return total-arrSum"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def missingNumber(self, nums: List[int]) -> int:\n",
    "        for i in range(len(nums)+1):\n",
    "            if i not in nums:\n",
    "                return i"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def missingNumber(self, nums: List[int]) -> int:\n",
    "        index = 0\n",
    "        while index <= len(nums):\n",
    "            if index not in nums:\n",
    "                return index\n",
    "            index += 1\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def missingNumber(self, nums: List[int]) -> int:\n",
    "        mylist = []\n",
    "        for i in nums:\n",
    "            mylist.append(i)\n",
    "        for i in range(0,len(mylist) + 1):\n",
    "            if mylist.count(i) == 0:\n",
    "                return i"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def missingNumber(self, nums: List[int]) -> int:\n",
    "        xor = 0\n",
    "        for i, num in enumerate(nums):\n",
    "            xor ^= i ^ num\n",
    "        return xor ^ len(nums)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def missingNumber(self, nums: List[int]) -> int:\n",
    "        l = len(nums)\n",
    "        return l * (l + 1)  // 2 - sum(nums)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def missingNumber(self, nums: List[int]) -> int:\n",
    "        nums=sorted(nums)\n",
    "        n=len(nums)\n",
    "        for i in range(0,n+1):\n",
    "            if i not in nums:\n",
    "                return i"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def missingNumber(self, nums: List[int]) -> int:\n",
    "        return [i for i in range(len(nums)+1) if i not in nums][0]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def missingNumber(self, nums: List[int]) -> int:\n",
    "        n = len(nums) + 1\n",
    "        return ((0 + n - 1) * n) // 2 - sum(nums)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def missingNumber(self, nums: List[int]) -> int:\n",
    "        nums.sort()\n",
    "        if len(nums)==nums[-1]:\n",
    "            for i in range(len(nums)):\n",
    "                if nums[i]!=i:\n",
    "                    return i\n",
    "        else:\n",
    "            return len(nums)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def missingNumber(self, nums: List[int]) -> int:\n",
    "        s = sum(nums)\n",
    "        num_count = len(nums)\n",
    "        target = num_count * (num_count + 1) // 2\n",
    "        return target - s\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def missingNumber(self, nums: List[int]) -> int:\n",
    "        index = 0\n",
    "        while index <= len(nums):\n",
    "            if index not in nums:\n",
    "                return index\n",
    "            index += 1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def missingNumber(self, nums: List[int]) -> int:\n",
    "        nums=sorted(nums)\n",
    "        l=len(nums)+1\n",
    "        total_num=[i for i in range (l)]\n",
    "        for num in total_num:\n",
    "            if num not in nums:\n",
    "                lose_num=num\n",
    "            else:\n",
    "                continue\n",
    "        return lose_num"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def missingNumber(self, nums: List[int]) -> int:\n",
    "        return list(set([i for i in range(len(nums)+1)])^set(nums))[0]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from typing import List\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def missingNumber(self, nums: List[int]) -> int:\n",
    "        nums += [-1] * 1\n",
    "        for i in range(len(nums)):  # 最坏（501234 -1）\n",
    "            while nums[i] != i and nums[i] != -1:  # 当前位置可能交换不止一次（5231 -1 -1）\n",
    "                temp = nums[i]\n",
    "                nums[i] = nums[nums[i]]\n",
    "                nums[temp] = temp\n",
    "        # for num in nums:\n",
    "        #     if num == -1:\n",
    "        return nums.index(-1)\n",
    "\n",
    "\n",
    "if __name__ == '__main__':\n",
    "    # print(Solution.missingNumber(Solution, nums=[3, 0, 1]))\n",
    "    print(Solution.missingNumber(Solution, nums=[9, 6, 4, 2, 3, 5, 7, 0, 1]))\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def missingNumber(self, nums: List[int]) -> int:\n",
    "        return list(set([i for i in range(len(nums)+1)])^set(nums))[0]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def missingNumber(self, nums: List[int]) -> int:\n",
    "        nums.sort()\n",
    "        nums_a = list(range(0, nums[-1] + 1))\n",
    "        print(nums_a)\n",
    "        if len(nums) == len(nums_a):\n",
    "            return nums[-1] + 1\n",
    "        res = list(set(nums) ^ set(nums_a))\n",
    "        return res[0]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def missingNumber(self, nums: List[int]) -> int:\n",
    "        hashmap=Counter(nums)\n",
    "        n=len(nums)+1\n",
    "        for i in range(n):\n",
    "            if i not in hashmap:\n",
    "                return i"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def missingNumber(self, nums: List[int]) -> int:\n",
    "        nums.sort()\n",
    "        nums_a = list(range(0, nums[-1] + 1))\n",
    "        print(nums_a)\n",
    "        if len(nums) == len(nums_a):\n",
    "            return nums[-1] + 1\n",
    "        res = list(set(nums) ^ set(nums_a))\n",
    "        return res[0]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def missingNumber(self, nums: List[int]) -> int:\n",
    "        s=set(nums)\n",
    "        for i in range(len(nums)+1):\n",
    "            if i not in s:\n",
    "                return i\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def missingNumber(self, nums: List[int]) -> int:\n",
    "        a=list(range(0,len(nums)+1))\n",
    "        return list(set(a)^set(nums))[0]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from typing import List, Optional\n",
    "from collections import Counter\n",
    "class Solution:\n",
    "    def missingNumber(self, nums: List[int]) -> int:\n",
    "        nums.sort(reverse=False)\n",
    "        nums_ = Counter(nums)\n",
    "        for i in range(len(nums) + 1):\n",
    "            if nums[-1] == 0:\n",
    "                return 1\n",
    "            elif i not in nums_:\n",
    "                return i\n",
    "\n",
    "\n",
    "if __name__ == \"__main__\":\n",
    "    function = Solution()\n",
    "    nums = [0]\n",
    "    res = function.missingNumber(nums)\n",
    "    print(res)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def missingNumber(self, nums: List[int]) -> int:\n",
    "        d = {}\n",
    "        for num in nums:\n",
    "            d[num] = 1\n",
    "        for i in range(len(nums) + 1):\n",
    "            if i not in d.keys():\n",
    "                return i"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def missingNumber(self, nums: List[int]) -> int:\n",
    "        dic = collections.defaultdict(int)\n",
    "        for i,x in enumerate(nums):\n",
    "            dic[x] = i\n",
    "        n = len(nums)\n",
    "        for i in range(n+1):\n",
    "            if i not in dic:\n",
    "                return i"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def missingNumber(self, nums: List[int]) -> int:\n",
    "        s = set(nums)\n",
    "        for i in range(len(nums) + 1):\n",
    "            if i not in s:\n",
    "                return i"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def missingNumber(self, nums: List[int]) -> int:\n",
    "        \n",
    "        a = set(range(0,len(nums)+1))\n",
    "        for i in a:\n",
    "            if i in nums:\n",
    "                continue\n",
    "            else:\n",
    "                return i"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def missingNumber(self, nums: List[int]) -> int:\n",
    "        n = len(nums)\n",
    "        dict_nums = {}\n",
    "        for i in nums:\n",
    "            dict_nums[i] = 1\n",
    "\n",
    "        for i in range(0,n+1):\n",
    "            if i not in dict_nums.keys():\n",
    "                return i\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def missingNumber(self, nums: List[int]) -> int:\n",
    "        s = set(nums)\n",
    "        for i in range(len(nums) + 1):\n",
    "            if i not in s:\n",
    "                return i\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def missingNumber(self, q: List[int]) -> int:\n",
    "        s = set(q)\n",
    "        for i in range(len(q) + 1):\n",
    "            if i not in s:\n",
    "                return i\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def missingNumber(self, nums: List[int]) -> int:\n",
    "        set_nums = set(nums)\n",
    "        for i in range(max(nums)):\n",
    "            if i not in set_nums:\n",
    "                return i\n",
    "        return max(nums) + 1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def missingNumber(self, nums: List[int]) -> int:\n",
    "        s = set(nums)\n",
    "        for i in range(len(nums) + 1):\n",
    "            if i not in s:\n",
    "                return i"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "\tdef missingNumber(self, nums: List[int]) -> int:\n",
    "\t\tnum_set = set(nums)\n",
    "\t\tfor i in range(len(nums) + 1):\n",
    "\t\t\tif i not in num_set:\n",
    "\t\t\t\treturn i\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def missingNumber(self, nums: List[int]) -> int:\n",
    "        memo = set(nums)\n",
    "        for i in range(len(nums)+1):\n",
    "            if i not in memo:\n",
    "                return i"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def missingNumber(self, nums: List[int]) -> int:\n",
    "        hmap = set(nums)\n",
    "        for i in range(len(nums)+1):\n",
    "            if i not in hmap:\n",
    "                return i"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def missingNumber(self, nums: List[int]) -> int:\n",
    "        # for i in range(len(nums)):\n",
    "        #     if nums[i] == len(nums):\n",
    "        #         for j in range(len(nums)):\n",
    "        #             if nums[j] != len(nums) -1:\n",
    "        #                 return len(nums) - 1\n",
    "        #     elif num[i] == 0:\n",
    "        #         for j in range(nums):\n",
    "        #             if nums[j] - 0 != 1:\n",
    "        #                 return 1\n",
    "        #     else:\n",
    "        #         for j in range(len(nums)):\n",
    "        #             if num[j] - num[i] != 1:\n",
    "        #                 return num[i] + 1\n",
    "        s = set(nums)\n",
    "        for i in range(len(nums) + 1):\n",
    "            if i not in s:\n",
    "                return i"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "\tdef missingNumber(self, nums: List[int]) -> int:\n",
    "\t\tnums = set(nums)\n",
    "\t\tfor i in range(len(nums) + 1):\n",
    "\t\t\tif i not in nums:\n",
    "\t\t\t\treturn i\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def missingNumber(self, nums: List[int]) -> int:\n",
    "        s = set(nums)\n",
    "        for i in range(len(nums) + 1):\n",
    "            if i not in s:\n",
    "                return i\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def missingNumber(self, nums: List[int]) -> int:\n",
    "        List = set(nums)\n",
    "        for i in range(len(List)+1):\n",
    "            if i not in List:\n",
    "                return i\n",
    "                break\n",
    "        \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def missingNumber(self, nums: List[int]) -> int:\n",
    "        List = set(nums)\n",
    "        for i in range(len(List)+1):\n",
    "            if i not in List:\n",
    "                return i\n",
    "            \n",
    "        \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def missingNumber(self, nums: List[int]) -> int:\n",
    "        visited = set(nums)\n",
    "        ma = len(nums)\n",
    "        mi = 0\n",
    "\n",
    "        for num in nums:\n",
    "            if num != mi and num - 1 not in visited:\n",
    "                return num - 1\n",
    "            if num != ma and num + 1 not in visited:\n",
    "                return num + 1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def missingNumber(self, nums: List[int]) -> int:\n",
    "        list_sum = 0\n",
    "        complete_sum = 0\n",
    "        for i in range(len(nums)):\n",
    "            list_sum += nums[i]\n",
    "            complete_sum += i\n",
    "        complete_sum += len(nums)\n",
    "        return complete_sum - list_sum"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def missingNumber(self, nums):\n",
    "        \"\"\"\n",
    "        :type nums: List[int]\n",
    "        :rtype: int\n",
    "        \"\"\"\n",
    "        for i in range(len(nums)+1):\n",
    "            try:\n",
    "                nums.remove(i)\n",
    "            except Exception as e:\n",
    "                return i"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def missingNumber(self, nums):\n",
    "        \"\"\"\n",
    "        :type nums: List[int]\n",
    "        :rtype: int\n",
    "        \"\"\"\n",
    "        n = len(nums)\n",
    "        return n * (n + 1) // 2 - sum(nums)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def missingNumber(self, nums: 'List[int]') -> 'int':\n",
    "        n = len(nums)\n",
    "        s = sum(list(range(n + 1)))\n",
    "        res = s - sum(nums)\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def missingNumber(self, nums):\n",
    "        \"\"\"\n",
    "        :type nums: List[int]\n",
    "        :rtype: int\n",
    "        \"\"\"\n",
    "        n = len(nums)\n",
    "        n_tag = [0] * (n+1)\n",
    "        for i in nums:\n",
    "            n_tag[i] = 1\n",
    "        for index, i in enumerate(n_tag):\n",
    "            if i == 0:\n",
    "                return index"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def missingNumber(self, nums: List[int]) -> int:\n",
    "        ll=len(nums)\n",
    "        sum=0\n",
    "        for i in nums:\n",
    "            sum+=i\n",
    "        return ll*(ll+1)//2-sum"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def missingNumber(self, nums):\n",
    "        \"\"\"\n",
    "        :type nums: List[int]\n",
    "        :rtype: int\n",
    "        \"\"\"\n",
    "        n = len(nums);\n",
    "        return int(n*(n+1)/2) - sum(nums)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def missingNumber(self, nums: 'List[int]') -> 'int':\n",
    "        s = set(nums)\n",
    "        for i in range(len(nums)+1):\n",
    "            if i not in s:\n",
    "                return i\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def missingNumber(self, nums: 'List[int]') -> int:\n",
    "        m = max(nums)\n",
    "        s = set(range(m + 1))\n",
    "        for x in nums:\n",
    "            s.remove(x)\n",
    "        l = list(s)\n",
    "        if len(l) == 0:\n",
    "            return m + 1\n",
    "        else:\n",
    "            return l[0]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def missingNumber(self, nums):\n",
    "        \"\"\"\n",
    "        :type nums: List[int]\n",
    "        :rtype: int\n",
    "        \"\"\"\n",
    "        lPoint=len(nums)\n",
    "        if lPoint==0:\n",
    "            return 0\n",
    "        Nmax=max(nums)\n",
    "        s=set(nums)\n",
    "        for i in range(Nmax,-1,-1):\n",
    "            if i in s:\n",
    "                continue\n",
    "            else:\n",
    "                return i\n",
    "        return Nmax+1\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def missingNumber(self, nums):\n",
    "        \"\"\"\n",
    "        :type nums: List[int]\n",
    "        :rtype: int\n",
    "        \"\"\"\n",
    "        num_set = set(nums)\n",
    "        n = len(nums) + 1\n",
    "        for number in range(n):\n",
    "            if number not in num_set:\n",
    "                return number"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def missingNumber(self, nums):\n",
    "        \"\"\"\n",
    "        :type nums: List[int]\n",
    "        :rtype: int\n",
    "        \"\"\"\n",
    "        \n",
    "        np=0\n",
    "        i=0\n",
    "        while i<len(nums):\n",
    "            print(i)\n",
    "            if nums[i]==len(nums):\n",
    "                np=1\n",
    "                i+=1\n",
    "                continue\n",
    "            if nums[i]!=i:\n",
    "                temp=nums[i]\n",
    "                nums[i]=nums[temp]\n",
    "                nums[temp]=temp\n",
    "                continue\n",
    "            else:\n",
    "                i+=1\n",
    "        if np==0:\n",
    "            return(len(nums))\n",
    "        else:\n",
    "            for i in range(len(nums)):\n",
    "                if nums[i]!=i:\n",
    "                    return(i)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def missingNumber(self, nums):\n",
    "        \"\"\"\n",
    "        :type nums: List[int]\n",
    "        :rtype: int\n",
    "        \"\"\"\n",
    "        from functools import reduce\n",
    "        nums.extend([i for i in range(len(nums) + 1)])\n",
    "        return reduce(lambda x, y: x ^ y, nums)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def missingNumber(self, nums):\n",
    "        \"\"\"\n",
    "        :type nums: List[int]\n",
    "        :rtype: int\n",
    "        \"\"\"\n",
    "        dict={}\n",
    "        n=len(nums)\n",
    "        for j in range(n):\n",
    "            dict[nums[j]]=j\n",
    "        for i in range(n+1):\n",
    "            if i not in dict:\n",
    "                return i\n",
    "        \n",
    "        \n",
    "        \n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def missingNumber(self, nums):\n",
    "        \"\"\"\n",
    "        :type nums: List[int]\n",
    "        :rtype: int\n",
    "        \"\"\"\n",
    "        dnums = {}\n",
    "        for i in range(len(nums) + 1):\n",
    "            dnums[i] = dnums.get(i, 0) + 1\n",
    "\n",
    "        for item in nums:\n",
    "            dnums.pop(item)\n",
    "\n",
    "        return list(dnums.keys())[0]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def missingNumber(self, nums):\n",
    "        import collections\n",
    "        res = [0]\n",
    "        for i in range(1, len(nums)+1):\n",
    "            res.append(i)\n",
    "            res.append(nums[i-1])\n",
    "        res_dic = collections.Counter(res)\n",
    "        for i in res_dic:\n",
    "            if res_dic[i] == 1:\n",
    "                return i\n",
    "        return False\n",
    "        \"\"\"\n",
    "        :type nums: List[int]\n",
    "        :rtype: int\n",
    "        \"\"\""
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def missingNumber(self, nums: 'List[int]') -> 'int':\n",
    "        nums.sort()\n",
    "        if len(nums) == 1:\n",
    "            if nums[0] == 0:\n",
    "                return 1\n",
    "            if nums[0] ==1:\n",
    "                return 0\n",
    "        elif nums[-1] != len(nums):\n",
    "            return len(nums)\n",
    "        \n",
    "        else:\n",
    "            for i in range(len(nums)):\n",
    "                if nums[i] != i:\n",
    "                    return i\n",
    "                    "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def missingNumber(self, nums: 'List[int]') -> 'int':\n",
    "        return int((len(nums)+1)*len(nums)/2 - sum(nums))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def missingNumber(self, nums: List[int]) -> int:\n",
    "        if nums==[0]:\n",
    "            return 1\n",
    "        if nums==[1]:\n",
    "            return 0\n",
    "        if 0 not in nums:\n",
    "            return 0\n",
    "        n=max(nums)\n",
    "        sum1=0\n",
    "        for i in range(n+1):\n",
    "            sum1+=i\n",
    "  \n",
    "        if sum1==sum(nums):\n",
    "\n",
    "            return n+1\n",
    "        else:\n",
    "            return sum1-sum(nums)\n",
    "        \n",
    "        \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def missingNumber(self, nums: List[int]) -> int:\n",
    "        nums.append(0)\n",
    "        for item in nums[:-1]:\n",
    "            nums[item] = -1\n",
    "        for i in range(0, len(nums)):\n",
    "            if nums[i] != -1:\n",
    "                return i"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def missingNumber(self, nums: List[int]) -> int:\n",
    "        if not nums:\n",
    "            return 0\n",
    "        max_temp = 0\n",
    "        for i in range(len(nums)):\n",
    "            cur = nums[i]\n",
    "            while cur != -1:\n",
    "                temp = -1\n",
    "                if cur != len(nums):\n",
    "                    temp = nums[cur]\n",
    "                    nums[cur] = -1\n",
    "\n",
    "                cur = temp\n",
    "        \n",
    "        for i in range(len(nums)):\n",
    "            if nums[i] != -1:\n",
    "                return i\n",
    "        return len(nums)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def missingNumber(self, nums) -> int:\n",
    "        n = len(nums)\n",
    "        for i in range(n+1):\n",
    "            if i not in nums:\n",
    "                return i\n",
    "            else:\n",
    "                nums.remove(i)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def missingNumber(self, nums: List[int]) -> int:\n",
    "        n = len(nums)\n",
    "        left = 0\n",
    "        right = n\n",
    "        while right > left:\n",
    "            mid = (left + right) // 2\n",
    "            count = 0\n",
    "            for i in range(n):\n",
    "                if nums[i] <= mid:\n",
    "                    count += 1\n",
    "            if count < mid + 1:\n",
    "                right = mid\n",
    "            else:\n",
    "                left = mid + 1\n",
    "        return right"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\r\n",
    "    def missingNumber(self, nums: List[int]) -> int:\r\n",
    "        nums.sort()\r\n",
    "        if nums[0] != 0:\r\n",
    "            return 0\r\n",
    "        else:\r\n",
    "            for i in range(0, len(nums) - 1):\r\n",
    "                if nums[i + 1] - nums[i] > 1:\r\n",
    "                    return nums[i] + 1\r\n",
    "            return nums[-1] + 1\r\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def missingNumber(self, nums: List[int]) -> int:\n",
    "        return sum(range(0, len(nums)+1)) - sum(nums)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def missingNumber(self, nums: List[int]) -> int:\n",
    "        num_set = set(nums)\n",
    "        for i in range(len(nums)+1):\n",
    "            if i not in num_set:\n",
    "                return i"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def missingNumber(self, nums: List[int]) -> int:\n",
    "        i=0\n",
    "        temp=0\n",
    "        while i<len(nums):\n",
    "            if nums[i]==i:\n",
    "                nums[i]=-1\n",
    "                i+=1\n",
    "            elif nums[i]==-1 or nums[i]==len(nums):\n",
    "                i+=1\n",
    "            else:\n",
    "                temp=nums[nums[i]]\n",
    "                nums[nums[i]]=-1\n",
    "                nums[i]=temp\n",
    "        for i in nums:\n",
    "            if i!=-1: return nums.index(i)\n",
    "        return len(nums)\n",
    "        \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def missingNumber(self, nums: List[int]) -> int:\n",
    "        nums.sort()\n",
    "        for i in range(len(nums)):\n",
    "            if i != nums[i]:\n",
    "                return i\n",
    "        return len(nums)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def missingNumber(self, nums: List[int]) -> int:\n",
    "        N = len(nums)\n",
    "        # 高斯公式：0 + 1 + 2 + ... + N = 1 + 2 + ... + N = (1 + N) * N // 2\n",
    "        s = sum(nums)\n",
    "        s2 = (1 + N) * N // 2\n",
    "        return s2 - s"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def missingNumber(self, nums: List[int]) -> int:\n",
    "        # sum1 = sum(nums)\n",
    "        # sum2 = sum(range(0,len(nums)+1))\n",
    "        # ans = sum2 - sum1\n",
    "        ans = len(nums)*(len(nums)+1) // 2 - sum(nums)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def missingNumber(self, nums: List[int]) -> int:\n",
    "        ret = 0\n",
    "        for i in range(len(nums)):\n",
    "            ret ^= ((i+1)^(nums[i]))\n",
    "        return ret"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def missingNumber(self, nums: List[int]) -> int:\n",
    "        n=len(nums)\n",
    "        m=[-1]*(n+1)\n",
    "        for i in range(n):\n",
    "            m[nums[i]]=nums[i]\n",
    "        a=-1\n",
    "        for i in range(n+1):\n",
    "            if m[i]<0:\n",
    "                a=i\n",
    "        return a"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def missingNumber(self, nums: List[int]) -> int:\n",
    "        n = len(nums)\n",
    "        pool = set(list(range(0,n+1)))\n",
    "        for e in nums:\n",
    "            pool.remove(e)\n",
    "        return list(pool)[0]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def missingNumber(self, nums: List[int]) -> int:\n",
    "        for i in range(len(nums)+1):\n",
    "            if i not in nums:\n",
    "                return i\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def missingNumber(self, nums: List[int]) -> int:\n",
    "        # if len(nums) == 1 :\n",
    "        #     if nums[0] = 0 :\n",
    "        #         return 1\n",
    "        #     else :\n",
    "        #         return 0\n",
    "        # elif len(nums) > 1 and len(nums) <5 :\n",
    "\n",
    "        # else :\n",
    "        #     nums.sort()\n",
    "        #     i = 1 \n",
    "        #     j = len(nums)- 2\n",
    "        #     while i < j :\n",
    "        #         if nums[i] + nums[j] < nums[0] + nums[len(nums)-1] :\n",
    "        #             return nums[j]+1\n",
    "        #         elif nums[i] + nums[j] > nums[0] + nums[len(nums)-1] :\n",
    "        #             return nums[i]-1\n",
    "        #         else :\n",
    "        #             i += 1\n",
    "        #             j -= 1\n",
    "        \n",
    "        for i in range(0,len(nums)+1) :\n",
    "            if i not in nums :\n",
    "                return i "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def missingNumber(self, nums: List[int]) -> int:\n",
    "        a=[]\n",
    "        n=len(nums)\n",
    "        nums.sort()\n",
    "        for i in range(0,n+1):\n",
    "            if i in nums:\n",
    "                pass\n",
    "            else:\n",
    "                a.append(i)\n",
    "                print(a)\n",
    "        for j in range(len(a)):\n",
    "            pass\n",
    "        return a[j]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def missingNumber(self, nums: List[int]) -> int:\n",
    "        num = len(nums)\n",
    "        lst = list(range(0, num + 1))\n",
    "        for i in nums:\n",
    "            if i in lst:\n",
    "                lst.remove(i)\n",
    "        return lst[0\n",
    "        ]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def missingNumber(self, nums: List[int]) -> int:\n",
    "        list1 = set(nums)\n",
    "        n = 0\n",
    "        for i in list1:\n",
    "            if i != n:\n",
    "                return n\n",
    "            n = n + 1\n",
    "        return n"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
